// m
// 给定一个数组nums，nums[i]代表第i间房屋存放的金额，假设房屋可以围城一圈，最后一间房屋跟第一间房屋可以相连，相邻的房屋装有防盗系统，假如相邻的两间房屋同时被偷
// 系统就会报警

// 要求：假如你是一名专业的小偷，计算在不触动报警装置的情况下，一夜之间能偷窃到的最高金额

// 解题思路，动态规划
// 如果房间总数大于等于3间，偷窃了第1间就不能偷窃最后一间房屋，同样偷窃了最后一间房屋则不能偷窃第一间房屋
// 假设总共房屋数量为size，这种情况可以转换为分别求解[0, size-2]和[1, size - 1]范围下，首尾不相连的房屋所能偷窃的最高金额，然后再取这两种情况下的最大值，而这两种情况
// 就和打家劫舍的解题思路一样了

// 时间复杂度： O(n)
// 空间复杂度：O(n)

function helper(nums) {
    let size = nums.length
    if (size === 1) {
        return nums[0]
    }
    if (size === 2) {
        return Math.max(nums[0], nums[1])
    }
    let dp = new Array(size).fill(0)
    dp[0] = nums[0]
    dp[1] = Math.max(nums[0], nums[1])

    for (let i = 2; i < size; i++) {
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
    }
    return dp[size - 1]
}

function rob(nums) {
    let size = nums.length
    if (size === 1) {
        return nums[0]
    }
    let ans1 = helper(nums.slice(1))
    let ans2 = helper(nums.slice(0, size - 1))
    return Math.max(ans1, ans2)
}

let nums = [2, 7, 9, 3, 1]
console.log(rob(nums));